/*!
 Temelia - AVL tree samples.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/samples.h"
#include <temelia/avl_tree.h>

static void sample1()
{
	avl_tree_t avl, aux;
	int **x, i, N = 100;

	PRINT("\n\n Sample 1 started \n\n");

	x = int_array_new(2 * N, 100);
	avl = avl_tree_new(x[0]);

	for (i = 1; i < N; i++)
	{
		PRINT("Inserez %d.\n", x[i][0]);
		aux = avl_tree_insert(&avl, x[i], int_compare, NULL, 1);
		//avl_tree_show_indented(avl, int_level_handler, NULL);
	}

	PRINT("Min = %d, Max = %d\n", *(int *) avl_tree_get_key(avl_tree_get_min(
							avl)), *(int *) avl_tree_get_key(avl_tree_get_max(avl)));

	avl_tree_show_indented(avl, int_level_handler, NULL);

	for (i = 0; i < N - 1; i++)
	{
		PRINT("\nSterg %d\n", x[i][0]);
		if (avl && avl_tree_remove(&avl, x[i], int_compare, NULL, 1))
			PRINT("Nu l-am gasit ....\n");
	}

	PRINT("\n\nArborele ramas este :\n");
	avl_tree_show_indented(avl, int_level_handler, NULL);

	/*
	 * Adaug primele N numere naturale in AVL si apoi testez functia de cautare.
	 */
	x[0][0] = 0;
	avl = avl_tree_new(x[0]);

	for (i = 1; i < N; i++)
	{
		x[i][0] = i;
		avl_tree_insert(&avl, x[i], int_compare, NULL, 1);
	}

	PRINT("\n\nNoul arborele este :\n");
	avl_tree_show_indented(avl, int_level_handler, NULL);

	for (i = 0; i < 2 * N; i++)
	{
		x[i][0] = i;
		if (avl_tree_search(avl, x[i], int_compare, NULL) == NULL)
			PRINT("Nu am gasit %d.\n", x[i][0]);
		else
			PRINT("Am gasit %d.\n", x[i][0]);
	}

	avl_tree_delete(avl);

	for (i = 0; i < 2 * N; i++)
		free(x[i]);
	free(x);

	PRINT("\n\n Sample 1 ended \n\n");
}

static void sample2()
{
	int i = 0, N = 100, **x;
	avl_tree_t avl1, avl2;

	PRINT("\n\n Sample 2 started \n\n");

	x = int_array_new(N, 1000);
	avl1 = avl_tree_new(x[0]);
	avl2 = avl_tree_new(x[0]);

	// Stress test.
	for (i = 0; i < N; i++)
		avl_tree_delete_node(avl_tree_new(NULL));

	for (i = 1; i < N; i++)
	{
		avl_tree_insert(&avl1, x[i], int_compare, NULL, 1);
		avl_tree_insert(&avl2, x[i], int_compare, NULL, 1);
	}

	PRINT("Compare = %d\n", avl_tree_compare_trees(avl1, avl2, int_compare, NULL));
	PRINT("Empty = %d, %d\n", avl_tree_is_empty(avl1), avl_tree_is_empty(NULL));

	for (i = 0; i < N; i++)
		free(x[i]);
	free(x);

	avl_tree_delete(avl1);
	avl_tree_delete(avl2);

	PRINT("\n\n Sample 2 ended \n\n");
}

static void sample3()
{
	avl_tree_t avl;
	int **x, i, N = 100;

	PRINT("\n\n Sample 3 started \n\n");

	x = int_array_new(N, 100);
	x[0][0] = 0;
	avl = avl_tree_new(x[0]);

	for (i = 1; i < N; i++)
	{
		x[i][0] = i;
		avl_tree_insert(&avl, x[i], int_compare, NULL, 1);
	}

	avl_tree_show_indented(avl, int_level_handler, NULL);

	PRINT("\n\nRoot key %d\n", *(int *) avl_tree_get_key(avl));
	PRINT("Root : parent %p, left child %p, right child %p\n",
			avl_tree_get_parent(avl), avl_tree_get_left_child(avl),
			avl_tree_get_right_child(avl));

	PRINT("Inaltimea este %d\n", avl_tree_get_height(avl));

	PRINT("Adancime(min) = %d, Adancime(max) = %d\n", avl_tree_get_depth(
					avl_tree_get_min(avl)), avl_tree_get_depth(avl_tree_get_max(avl)));
	PRINT("Leaf(root) = %d, Leaf(min) = %d, Leaf(max) = %d\n", avl_tree_is_leaf(
					avl), avl_tree_is_leaf(avl_tree_get_min(avl)), avl_tree_is_leaf(
					avl_tree_get_max(avl)));

	PRINT("Size = %d\n", avl_tree_get_size(avl));

	avl_tree_delete(avl);

	for (i = 0; i < N; i++)
		free(x[i]);
	free(x);

	PRINT("\n\n Sample 3 ended \n\n");

}

static void sample4()
{
	avl_tree_t avl;
	int i, N = 1000;
	void *key;

	PRINT("\n\n Sample 4 started \n\n");

	avl = avl_tree_new(NULL);

	for (i = 0; i < N; i++)
	{
		//key = int_new(i);
		key = int_new(rand() % 1000);

		// If key already exists in AVL tree then delete it now
		if (avl_tree_insert(&avl, key, int_compare, NULL, 1) == NULL)
			int_delete(key, NULL);
	}

	PRINT("Arborele este %p:\n", avl);
	avl_tree_show_indented(avl, int_level_handler, NULL);

	PRINT("\nPreorder :\n");
	avl_tree_preorder(avl, int_handler, NULL);

	PRINT("\nInorder :\n");
	avl_tree_inorder(avl, int_handler, NULL);

	PRINT("\nReverse inorder :\n");
	avl_tree_reverse_inorder(avl, int_handler, NULL);

	PRINT("\nPostorder :\n");
	avl_tree_postorder(avl, int_handler, NULL);

	PRINT("\nLevel order :\n");
	avl_tree_level_order(avl, int_handler, NULL);

	avl_tree_level_order(avl, int_delete, NULL);

	avl_tree_delete(avl);

	PRINT("\n\n Sample 4 ended \n\n");
}

static void sample5()
{
	avl_tree_t avl;
	int i, N = 10;
	void *keys[10];

	PRINT("\n\n Sample 4 started \n\n");

	avl = avl_tree_new(NULL);

	for (i = 0; i < N; i++)
	{
		//key = int_new(i);
		keys[i] = int_new(rand() % 1000);

		// If key already exists in AVL tree then delete it now
		if (avl_tree_insert(&avl, keys[i], int_compare, NULL, 1) == NULL)
			int_delete(keys[i], NULL);
	}

	PRINT("Arborele este %p:\n", avl);
	avl_tree_show_indented(avl, int_level_handler, NULL);

	for (i = 0; i < 10; i++)
	{
		PRINT("Sterg %d\n", *(int *) keys[i]);
		avl_tree_remove(&avl, keys[i], int_compare, NULL, 1);
	}

	PRINT("Dupa stergere, arborele este %p:\n", avl);
	avl_tree_show_indented(avl, int_level_handler, NULL);

	for (i = 0; i < N; i++)
		int_delete(keys[i], NULL);

	avl_tree_delete(avl);
}

void run_avl_tree_samples()
{
	sample1();
	sample2();
	sample3();
	sample4();
	sample5();
}
